import java.util.List;

/**
 * 力扣206 -  链表反转  反转单向链表  黑马算法上 P57-P61
 * public class  ListNode{
 * int val;
 * ListNode  next;
 * ListNode(){}
 * ListNode(int val){this.val = val}
 * ListNode(int val , ListNode next){ this.val = val , this.next = next}
 * }
 * <p>
 * 输入 [1,2,3,4,5]  输出  [5,4,3,2,1]
 */


public class LeetCode206 {

    /**
     * 方法一  ：遍历原链表， 创建新链表倒着放入新链表
     */
    public static ListNode reverseList(ListNode node1) {
        ListNode newListNode = null;
        while (node1 != null) {
            newListNode = new ListNode(node1.val, newListNode);
            node1 = node1.next;
        }
        return newListNode;
    }

    /**
     * 方法二  ：  从旧链表的头部 移除节点  放入到新链表的尾部， 但不每次都创建节点 而是用就节点
     */
    public static ListNode reverseList1(ListNode head) {
        MyList myList = new MyList(head);
        MyList result = new MyList(null);
        while (true) {
            ListNode listNode = myList.removeFirst();
            if (listNode == null) {
                break;
            }
            result.addFirst(listNode);
        }
        return result.head;
    }

    /**
     * 方法三： 递归
     */
    public static ListNode reverseListNode2(ListNode p) {
        if (p == null || p.next == null) {
            return p;
        }
        ListNode last = reverseListNode2(p.next);  //每次递归找到最后一个节点
        p.next.next = p;
        p.next = null;
        return last;
    }

    /**
     * 方法四： 从链表每次拿到第二个节点，将其从链表断开，插入头部，直到他为null为止
     *
     */
    public static ListNode reverseList3(ListNode o1) {
        if(o1 == null || o1.next == null){
            return o1;
        }
        ListNode o2 = o1.next;   //设置指针，旧头o1， o2(旧老二) 、新头n1，分别指向第一个节点
        ListNode n1 = o1;
        while (o2 != null) {         //指针后移，当o1在到结尾了就结束
            o1.next = o2.next;      //将o2节点从链表断开， 让o1的next指向o3
            o2.next = n1;           //把o2 放到 新链表的最前面， 因为新链表有一个n1，那就把o2的next指向n1
            n1 = o2;                //此时n1 是指向链表末尾，需要将n1指针重新指向新链表的第一个节点，也就是o2这个绩点
            o2 = o1.next;           //最后 循环进行到下一个，让o2指向下一个
        }
        return n1;
    }

    /**   每次都把o1的next 插入到链表头部，然后 o1指向他的下一个
     *   o1
     *   n1
     *   1 -> 2 -> 3 -> 4 -> 5 -> null
     *   n1  o1
     *   2 -> 1 -> 3 -> 4 -> 5 -> null
     *   n1       o1
     *   3 -> 2 -> 1 -> 4 -> 5 -> null
     *   n1             o1
     *   4 -> 3 -> 2 -> 1 -> 5 -> null
     *   n1                 o1
     *   5 -> 4 -> 3 -> 2 -> 1 -> null
     *
     * @param args
     */

    public static void main(String[] args) {
        ListNode node5 = new ListNode(5, null);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        System.out.println(node1);
        ListNode reverseList = reverseList(node1);
        System.out.println(reverseList);
//        ListNode reverseList1 = reverseList1(node1);
//        System.out.println(reverseList1);
//        ListNode reverseList2 = reverseListNode2(node1);
//        System.out.println(reverseList2);
        ListNode reverseList3 = reverseList3(node1);
        System.out.println(reverseList3);
    }

}


class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
    // 静态方法 of 用于创建链表
    public static ListNode of(int... values) {
        if (values == null || values.length == 0) {
            return null;
        }
        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        return head;
    }
}

class MyList {
    ListNode head;

    public MyList(ListNode listNode) {
        this.head = listNode;
    }

    public void addFirst(ListNode first) {
        first.next = head;
        head = first;
    }

    public ListNode removeFirst() {
        ListNode first = head;
        if (first != null) {
            head = first.next;
        }
        return first;
    }
}